package previous.Test_0216;

import java.util.Arrays;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //衣橱整理
    int [][] grid;
    int count;
    int m,n;
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    boolean[][] vis;
    public int wardrobeFinishing(int _m, int _n, int cnt) {
        m=_m;
        n=_n;
        vis=new boolean[m][n];
        grid=new int[m][n];
        dfs(0,0,cnt);
        return count;
    }
    public void dfs(int i,int j,int cnt){
        count++;
        vis[i][j]=true;
        for (int k = 0; k < 4; k++) {
            int sum=0;
            int x=dx[k]+i;
            int y=dy[k]+j;
            int a=x;
            int b=y;
            while(a!=0){
                sum+=a%10;
                a=a/10;
            }
            while(b!=0){
                sum+=b%10;
                b=b/10;
            }

            if(x>=0 && x<m && y>=0 && y<n && !vis[x][y]&& sum<=cnt){
                dfs(x,y,cnt);
            }
        }
    }
    //斐波拉契数
    public int fib1(int n) {
          return  dfs1(n);
    }
    public int dfs1(int n){
        if(n<=1){
            return n;
        }
        return dfs1(n-1)+dfs1(n-2);
    }
    int[] dp=new int[31];
    public int fib2(int n) {
        dp[0]=0;
        dp[1]=1;
        for (int i = 2; i <=n ; i++) {
            dp[i]=dp[i-2]+dp[i-1];
        }
        return  dp[n];
    }
    int[] memo=new int[31];
    public int fib(int n) {
        for (int i = 0; i < 31; i++) {
            memo[i] = -1;
        }
        return  dfs(n);
    }
    public int dfs(int n){
        //剪枝
        //备忘录中查找
        if(memo[n]!=-1){
            return memo[n];
        }
        if(n<=1){
            memo[n]=n;//放备忘录
            return n;
        }
        memo[n]= dfs(n-1)+dfs(n-2);//放备忘录里
        return memo[n];
    }
    //不同路径
    int[][] mo;
    public int uniquePaths1(int m, int n) {
        mo=new int[m+1][n+1];
        return dfs(m,n);
    }
    public int dfs(int i,int j){
        if(mo[i][j]!=0){
            return mo[i][j];
        }
        if(i==0 || j==0){
            mo[i][j]=0;
            return 0;
        }
        if(i==1 && j==1){
            mo[i][j]=1;
            return 1;
        }
        mo[i][j]=dfs(i-1,j)+dfs(i,j-1);
        return mo[i][j];
    }
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m+1][n+1];
        dp[1][1]=1;
        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if(i==1 && j==1) continue;
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];
    }
    //最长递增子序列
    public int lengthOfLIS1(int[] nums) {
        int len=nums.length;
        int[] dp=new int[len];
        int ret=0;
        Arrays.fill(dp,1);
        //最后一个元素开始遍历
        for (int i = len-1; i >=0 ; i--) {
            //当前元素的下一个元素开始遍历
            for (int j = i+1; j < len; j++) {
                if(nums[j]>nums[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            ret=Math.max(ret,dp[i]);
        }
        return ret;
    }

}
